home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Shareware Grab Bag
/
Shareware Grab Bag.iso
/
007
/
btsys.arc
/
BTISRT.C
< prev
next >
Wrap
Text File
|
1984-12-14
|
5KB
|
195 lines
/* btisrt */
#include <stdio.h>
#include <btextern.h>
int btisrt (filhand, key, datapt)
int filhand, datapt;
char key[];
/* main routine to insert key into btree */
{
int i,j,k,node,holdptr,*ip,klength,occurs;
char *cp,leaf;
int *new,*temp,last;
/* find place to insert the key */
if ((i = btplace (filhand, key)))
BTSETCOD (filhand, NULL, 60); /* set logic error */
/* this value is already stored in the stack by btplace */
klength = btfilar[filhand].keylen;
occurs = (LBLEN - 1) / (btfilar[filhand].keylen + 3);
j = pop ();
node = pop ();
leaf = 'Y';
again:
ip = btfilar[filhand].filbuf + (occurs - 1);
holdptr = *ip;
/* set up pointers to move keys over by one position */
ip2 = btfilar[filhand].filbuf + (occurs - 1); /* start of move */
ip1 = ip2 - 1; /* from where to move */
ip3 = btfilar[filhand].filbuf + j; /* till when to move */
while (ip1 >= ip3) {
*ip2-- = *ip1--;
}
/* now move keys */
cp2 = (char *)(btfilar[filhand].filbuf + occurs);
cp2 += (occurs - 1)*(klength + 1); /* where to move */
cp1 = cp2 - (klength + 1);
cp3 = (char *)(btfilar[filhand].filbuf + occurs);
cp3 += j*(klength + 1);
while (cp1 >= cp3) {
strcpy (cp2,cp1);
cp1 -= (klength + 1);
cp2 -= (klength + 1);
}
strcpy (cp2,key);
*ip2 = datapt; /* insert new key and pointer */
cp = (char *)btfilar[filhand].filbuf;
cp += (LBLEN - 1);
*cp = leaf;
cp = (char *)(btfilar[filhand].filbuf + occurs);
cp += (occurs - 1)*(klength + 1);
if ((i = strcmp (cp, "")) == 0) {
if ((i = btwrit (filhand, node)))
BTSETCOD (filhand, node, i); /* set write error */
return (0);
}
/* btdivd */
/* divides a node gets space and writes it out */
else {
if (!( new = (int*)calloc (LBLEN, (sizeof (char)))))
BTSETCOD (NULL, NULL, 7); /* no core */
if (!(temp = (int*)calloc (LBLEN, sizeof (char))))
BTSETCOD (NULL, NULL, 7); /* no core */
last = occurs / 2;
k = 0;
cp1 = btfilar[filhand].ikeyptr;
cp1 += last*(klength + 1); /* start of key move */
cp3 = btfilar[filhand].ikeyptr + occurs*(klength + 1);
cp2 = (char*)(new + occurs); /* init destination */
while (cp1 < cp3)
*cp2++ = *cp1++; /* move keys */
ip1 = btfilar[filhand].filbuf; /* start of pointer area */
ip3 = ip1 + occurs; /* end of pointers */
ip1 += last;
ip2 = new; /* init destination */
while (ip1 < ip3)
*ip2++ = *ip1++; /* move pointers */
*ip2 = holdptr;
while (++ip2 < (new + occurs))
*ip2 = NULL; /* zero all pointers */
cp3 = (char *)new + LBLEN; /* end of keys */
while (cp2 < cp3)
*cp2++ = '\0';
/* all keys have now been nulled */
/* set true flag */
*((char *)(new) + (LBLEN -1)) = leaf; /* keep old flag value */
/* move to temporary area */
movmem (btfilar[filhand].filbuf, temp, LBLEN);
movmem (new,btfilar[filhand].filbuf, LBLEN);
/* write new node */
if ((i = btwrit (filhand, (k = btgetsp (filhand)))))
BTSETCOD (filhand, k, i); /* set error */
movmem (temp, btfilar[filhand].filbuf, LBLEN);
cp1 = btfilar[filhand].ikeyptr;
cp1 += (last - 1)*(klength + 1); /* init pointers */
strcpy (key, cp1); /* store key */
/* now blank all keys and pointers that were moved */
ip1 = btfilar[filhand].filbuf;
ip3 = ip1 + occurs;
ip1 += last;
while (ip1 < ip3)
*ip1++ = NULL; /* zero all pointers */
cp1 = btfilar[filhand].ikeyptr;
cp1 += last*(klength + 1);
cp3 = btfilar[filhand].ikeyptr + occurs*(klength + 1);
while (cp1 < cp3)
*cp1++ = '\0'; /* null all keys */
/* now write out changed node */
if ((i = btwrit (filhand, node)))
BTSETCOD (filhand, node, i); /* set write error */
/* free buffers */
free (temp);
free (new);
} /* end if */
/* check if root node has been split */
datapt = node; /* save node value before popping stack */
j = pop ();
if ((node = pop ()) != NULL) {
if ((i = btread (filhand, node)))
BTSETCOD (filhand, node,i);
ip = btfilar[filhand].filbuf + j;
*ip = k;
cp = (char *)btfilar[filhand].filbuf;
cp += (LBLEN - 1);
leaf = 'N';
goto again;
}
else {
ip = btfilar[filhand].filbuf;
*ip++ = datapt;
*ip = k; /* value of new node in root */
cp = btfilar[filhand].ikeyptr;
strcpy (cp, key);
cp += (klength + 1);
strcpy (cp,'\0');
/* now clear out rest of new root */
ip1 = btfilar[filhand].filbuf + 2; /* starting place */
ip3 = btfilar[filhand].filbuf + occurs; /* ending place */
while (ip1 < ip3)
*ip1++ = NULL; /* null it baby ! */
cp1 = (char *)(btfilar[filhand].filbuf + occurs);
cp3 = cp1 + occurs*(klength + 1); /* end here */
cp1 += (klength + 1);
while (cp1 < cp3)
*cp1++ = '\0'; /* null keys */
*((char *)(btfilar[filhand].filbuf) + (LBLEN -1)) = 'N';
/* write out new root */
k = btgetsp (filhand); /* get a new node for new root */
if ((i = btwrit (filhand, k)))
BTSETCOD (filhand, k, i); /* set error code */
/* put new root value in control block */
btfilar[filhand].root = k;
} /* end if */
return (0);
} /* end btisrt */